A digital signature scheme is a public key cryptographic protocol involving a user and a signer. The signer owns a secret key and an associated public key. The user generates a message, generally for transmission over a network, such as the Internet. The signer uses his secret (or private) key to produce the digital signature of the message as an indication of the validity or authenticity of the message. Anyone who wishes to verify the authenticity of the signature can do so using only the signer's public key.
In conventional digital signature schemes the signer knows the content of the message to which the digital signature is being applied, and a signature algorithm (e.g. the well-known RSA algorithm) is used to generate a digital signature which is difficult or impossible to forge.
In a blind signature scheme, the user can obtain a digital signature on his message without letting the signer have information on the content of the message. A well-known blind signature scheme, developed by Prof. Dr. David Chaum, is described in EP-A-0 139 313. Blind signature schemes are often proposed for use in digital cash applications so as to enable an individual to purchase digital cash from a financial institution in a manner which prevents the financial institution from being able to trace the subsequent use of that cash.
In an ordinary blind signature scheme, if the signer signs a number of documents for different users then, when he is presented with one particular document that he has signed, he will not be able to determine when or for whom he signed that document. By way of contrast, in a fair blind signature scheme (FBSS), there is an additional participant, one or more trusted authorities (or “judges”), and the signer can identify which signature resulted from a given signing session with the help of the trusted authority (or of a quorum of trusted authorities if there is more than one).
If the signer has a transcript of a particular signing session then, with the help of the trusted authority, he can identify the signature-message pair resulting from that session: this is termed “signature tracing”. Conversely, if the signer has available a particular message-signature pair then, with the help of the trusted authority, he can determine the signing session at which this was generated: this is termed “session tracing”.
One component used in fair blind signature schemes is “zero-knowledge proofs of knowledge”. One entity (the “prover”) may need to prove to another entity (the “verifier”) that a certain statement (or predicate) is true. If the prover and verifier can perform an appropriate interactive procotol (an interactive proof of knowledge), the verifier can be convinced of the truth of the statement. The proof of knowledge protocol is termed “zero-knowledge” if, even after taking part in the proof of knowledge, the verifier has no knowledge of what the statement is (the verifier merely knows that it is true or “valid”). In the latter case, the verifier cannot himself prove the validity of the statement to others.
Although fair blind signature schemes enable a given digital signature to be linked to a given user, the user's message still remains private. Fair blind signature schemes have mainly been proposed in the context of applications where revocable anonymity is desirable, such as electronic auctions, and the fight against organized crime (e.g. the prevention of money laundering).
In order to be secure, a fair blind signature scheme should possess the properties of one-more unforgeability, blindness and traceability (tight revocation).
“One-more unforgeability” denotes the fact that it is computationally difficult to produce a k+1th valid signature under the fair blind signature scheme even if the intending forger has interacted with the signer k times (this can be designated “(k,k+1)-unforgeability”). This property should hold even if the interactions between the intending forger and the signer are performed in an adaptive and interleaving manner.
“Blindness” denotes the property whereby it is computationally difficult for anyone (other than the trusted authority) who is provided with a particular valid digital signature to generate information which enables identification of the user who conducted the signing session which yielded that signature. Similarly, it is computationally difficult for anyone (other than the trusted authority) who is provided with a transcript of a particular signing session to identify the signature which was produced in that session.
“Traceability (tight revocation)” denotes the property whereby it is difficult for anyone (except for the signer) to circumvent the tracing procedures built into the fair blind signature scheme. More particularly, it is computationally difficult for everyone (except the signer) to output a valid signature that cannot be traced by the trusted authority or that cannot be matched by the trusted authority to the corresponding user.
Various fair blind signature schemes have been proposed. See, for example, “Fair Blind Signatures” by M. Stadler et al, in Advances in Cryptology,—Eurocrypt '95, volume 921 of Lecture Notes in Computer Science, pp 209-219, Berlin, Springer-Verlag. However, most of the proposed schemes are either inefficient, insecure or only proven to be secure if non-standard assumptions are made.
One efficient fair blind signature scheme has been proposed by Abe and Ohkubo (see “Provably Secure Fair Blind Signatures with Tight Revocation” in Proceedings of Asiacrypt '01, volume 2248 of Lecture Notes in Computer Science, pp 583-601, Berlin, Springer-Verlag). The security of this scheme (that is, the unforgeability of the signatures) relies on the discrete logarithm problem. Although this scheme is claimed to offer polynomial security, in fact it only offers poly-logarithmic security (that is, only a poly-logarithmic number of signatures can be securely issued: this poly-logarithmic number being defined in terms of a security parameter).
The preferred embodiments of the present invention provide a fair blind signature scheme that is efficient and that allows a polynomial number of signatures to be securely issued.
Further features and advantages of the present invention will become apparent from the following description of a preferred embodiment thereof, given by way of example, illustrated by the accompanying drawing which indicates the main elements of the fair blind signature scheme of the preferred embodiment.
Before providing a detailed description of the fair blind signature process according to a preferred embodiment of the present invention, it is useful to recall certain basic principles of fair blind signature schemes and some mathematical notation.
It is considered unnecessary to give a formal definition of a fair blind signature scheme (FBSS) here because this is well-known in this field. However, the interested reader can refer to the Abe and Ohkubo paper cited above for such a definition, if desired.
It is considered sufficient to recall here that a FBSS involves three types of participants: users, U, who wish to have messages signed, a signer (s) who produces the blind digital signatures, and a trusted authority (TA) who can also be called a “judge”. In the fair blind signature scheme of the present invention three different kinds of protocols are used: a signature issuing protocol conducted between the user and the signer, allowing the user to obtain a signature of a message of his choice, a signature-submission protocol conducted between the user and anyone, allowing the user to submit a signature with a message, and the tracing protocols in which there is a signature-tracing protocol and/or a session-tracing protocol both conducted between the signer, S, and the trusted authority, TA.
It should be noted that the session-tracing protocol used in the preferred embodiment of the present invention enables the trusted authority to determine from a particular message-signature pair the identity of the user who conducted the signing session which led to generation of that pair. Thus, this preferred protocol can be designated a “user-tracing” protocol. In practice, tracing of the user is more useful than merely identifying the signing session that resulted in the generation of a particular message-signature pair. (In some schemes, it is necessary to search through a large database in order to determine which user conducted the signing session which has been identified by a true session-tracing protocol.)
In the description below the following mathematical notation will be used:
x ∈R E means that x is chosen uniformly, at random, from the set E—in other words x is chosen at random from the set E according to the uniform distribution.
If x is an integer, |x| denotes the binary size (or length) of x.
The set Id, means the set of integers running from 0 to d−1, in other words, it corresponds to the set {0, 1, 2, . . . , d−1}.
For an integer n,  denotes the residue class ring modulo n, and  denotes the multiplicative group of invertible elements in 
For an element α which is chosen uniformly at random in the set  (in other words, for α∈R  the order of α in  is denoted ord (α).
The subgroup of  generated by an element α chosen uniformly at random in  (in other words, generated by α∈R  is denoted α.
The set QR(n) denotes the set of all quadratic residues modulo n.
The symbol ∥ denotes the concatenation of two (binary) strings (or of binary representations of integers and group elements).
The symbol H denotes any convenient hash function.
SK(α:f(α, . . . ))(m) denotes a “signature of knowledge” on message m. By providing the signature of knowledge, SK, a prover demonstrates to a third party (“the verifier”) that he knows a value, α, which satisfies the equation defining the predicate, f.
SK(α,β:f(α, . . . )g(β, . . . ))(M) denotes a “signature of knowledge” on message M, demonstrating that the prover knows values α and β which satisfy the equation defining f and the equation defining g.
A “signature of knowledge” is a signature derived from a zero-knowledge proof of knowledge using the well-known Fiat-Shamir heuristic (see “How to Prove Yourself: Practical Solutions to Identification and Signature Problems” by A. Fiat and A. Shamir in Proceedings of Crypto '86, vol.263 of Lecture Notes in Computer Science, pp 186-194, Berlin, Springer-Verlag, 1987). If the underlying proof of knowledge is secure, a signature of knowledge derived therefrom can be shown to be secure in the random oracle model.
Depending upon the nature of the predicate(s), f, g, etc. referred to in the signature of knowledge, the prover will need to transmit different information to the verifier in order to establish the zero-knowledge proof of knowledge. Starting at page 13, some examples will be given of typical predicates and the information that can be transmitted by a prover in order to prove possession of a value which satisfies the associated predicate.